package com.fufu.algorithem.linklist;

/**
 * 约瑟夫问题：基于链表实现
 * @author: BlcakTiger
 * @date: 2023/2/10 21:03
 * @contact: hsf6661@163.com
 */
public class Josepfu约瑟夫 {
    public static void main(String[] args) {
        CircleSingleLinkedList singleLinkedList = new CircleSingleLinkedList();
        singleLinkedList.addBoy(5);
//        singleLinkedList.showBoy();
        singleLinkedList.countBoy(1,2,5);
    }


}

/**
 * 创建单向环形链表
 */
class CircleSingleLinkedList{

    /**
     * 创建first节点
     */
    private Boy first;

    /**
     * 添加Boy节点，需要为Boy指定编号
     * @param num Boy的指定编号
     */
    public void addBoy(int num){
        if (num<1){
            System.out.println("nums的值不正确！");
            return;
        }
        //辅助指针，帮助构成环形链表
        Boy curBoy = null;
        //使用for循环创建环形链表
        for (int i = 1; i <= num; i++) {
            //根据编号，创建小孩节点
            Boy boy = new Boy(i);
            //如果是第一个Boy
            if(i==1){
                first = boy;
                //构成环状
                first.setNext(first);
                //记录当前节点,以便下一次添加节点更改指向
                curBoy = first;
            }else{
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }


    /**
     * 显示Boy链表中的全部数据
     */
    public void showBoy(){
        //判断链表是否为空
        if (first==null){
            System.out.println("链表为空，Boy节点为空");
        }
        //因为first不能动，因此我们仍然使用一个辅助指针帮助完成遍历
        Boy curBoy = first;
        //循环遍历Boy链表
        while (true){
            System.out.printf("Boy编号：%d\n",curBoy.getNo());
            //若curBoy的下一个节点重新指向first，则表明指针已经执行尾部
            if (curBoy.getNext()==first){
                break;
            }
            //指针后移
            curBoy = curBoy.getNext();
        }
    }


    /**
     *根据用户的输入，计算小孩的出圈顺序
     * @param startNo 起始位置
     * @param countNum 数几下
     * @param nums 链表中的Boy节点数
     */
    public void countBoy(int startNo,int countNum,int nums){
        if (first==null){
            System.out.println("没有一个Boy");
        }else if(startNo<1 || startNo>nums){
            System.out.println("参数输入有误，请重新输入！");
            return;
        }
        //创建一个辅助指针
        Boy helper = first;
        //将辅助指针指向最后一个元素
        while (true){
            if (helper.getNext()==first){
                break;
            }
            helper = helper.getNext();
        }
        //在小孩报数前，应先将first指针移动到startNo处，因为是从startNo开始计数，helper对应在first前一个节点
        for (int i = 0; i < startNo-1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //当小孩报数时，让first指针和helper指针同时移动k-1次
        while (true){
            //当helper==first时，说明只有一个节点存在
            if(helper == first){
              break;
            }
            for (int i = 0; i < countNum-1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //这时first指针指向的节点就是要出圈的Boy
            System.out.println("小孩"+first.getNo()+"出圈");
            //将boy出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后出圈的小孩编号："+first.getNo());
    }
}

/**
 * 创建一个Boy类，表示节点
 */
class Boy{

    /**
     * 编号
     */
    private int no;
    /**
     * 指向下一个节点，默认null
     */
    private Boy next;

    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}
